package cn.springcloud.fix.demo.leecode;

import java.util.*;

public class Test07 {

    public static void main(String[] args) {
        Node node1 = new Node("a");
        Node node2 = new Node("b");
        Node node3 = new Node("c");
        Node node4 = new Node("d");
        Node node5 = new Node("e");
        Node node6 = new Node("f");
        Node node7 = new Node("g");

        node1.setLeft(node2);
        node1.setRight(node5);

        node2.setLeft(node3);
        node2.setRight(node4);

        node5.setLeft(node6);
        node5.setRight(node7);

        System.out.println("前序遍历-----------------");
        preOrder(node1);
        System.out.println("前序遍历-----------------");
        preOrder2(node1);

        System.out.println("打印所有树路径1-----------------");
        List<String> paths = new ArrayList<>();
        binaryTreePaths(node1, "", paths);
        paths.forEach(System.out::println);

        System.out.println("打印所有树路径2-----------------");
        List<String> pathss = binaryTreePaths2(node1);
        pathss.forEach(System.out::println);

        System.out.println("打印所有树的高度-----------------");
        System.out.println(heightOfTree(node1));

        System.out.println("层序遍历-----------------");
        levelOrder(node1);
    }

    // 树的高度
    private static int heightOfTree(Node node) {
        if (node == null) return 0;
        int h1 = heightOfTree(node.getLeft());
        int h2 = heightOfTree(node.getRight());
        return 1 + Math.max(h1, h2);
    }

    // 树的高度，非递归
    private static int heightOfTree2(Node node) {
        if (node == null) return 0;
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);
        int height = 0;
        int size = queue.size();
        while (!queue.isEmpty()) {
            Node n = queue.remove();
            size--;
            if (n.getLeft() != null) {
                queue.add(n.getLeft());
            }
            if (n.getRight() != null) {
                queue.add(n.getRight());
            }
            if (size == 0) {
                size = queue.size();
                height++;
            }
        }
        return height;
    }

    //层序遍历
    private static List<List<Object>> levelOrder(Node node) {
        List<List<Object>> result = new ArrayList<>();
        if (node == null) return result;
        List<Object> list = new ArrayList<>();
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);
        int size = queue.size();
        while (!queue.isEmpty()) {
            Node n = queue.remove();
            list.add(n.getVal());
            size--;
            if (n.getLeft() != null) {
                queue.add(n.getLeft());
            }
            if (n.getRight() != null) {
                queue.add(n.getRight());
            }
            if (size == 0) {
                size = queue.size();
                result.add(list);
                list = new ArrayList<>();
            }
        }
        for (List<Object> l : result) {
            System.out.println(l.toString());
        }
        return result;
    }

    //前序遍历
    private static void preOrder(Node node) {
        if (node == null) return;
        System.out.println(node.getVal());
        preOrder(node.getLeft());
        preOrder(node.getRight());
    }

    private static void preOrder2(Node node) {
        Stack<Node> stack = new Stack<>();
        stack.add(node);
        while (!stack.isEmpty()) {
            Node n = stack.pop();
            System.out.println(n.getVal());
            if (n.getRight() != null) {
                stack.add(n.getRight());
            }
            if (n.getLeft() != null) {
                stack.add(n.getLeft());
            }
        }
    }

    //打印二叉树所有路径
    private static void binaryTreePaths(Node node, String path, List<String> paths) {
        if (node == null) return;

        StringBuilder sb = new StringBuilder(path);
        sb.append(node.getVal().toString());

        if (node.getLeft() == null && node.getRight() == null) {  // 当前节点是叶子节点
            paths.add(sb.toString());
        } else {// 当前节点不是叶子节点，继续递归遍历
            binaryTreePaths(node.getLeft(), sb.toString(), paths);
            binaryTreePaths(node.getRight(), sb.toString(), paths);
        }
    }

    //打印二叉树所有路径
    private static List<String> binaryTreePaths2(Node node) {
        List<String> paths = new ArrayList<>();
        if (node == null) return paths;

        Queue<Node> nodeQueue = new LinkedList<>();
        nodeQueue.add(node);
        Queue<String> pathQueue = new LinkedList<>();
        pathQueue.add(node.getVal().toString());

        while (!nodeQueue.isEmpty()) {
            Node n = nodeQueue.remove();
            String path = pathQueue.remove();

            if (n.getLeft() == null && n.getRight() == null) {// 当前节点是叶子节点
                paths.add(path);
            } else {// 当前节点不是叶子节点
                if (n.getLeft() != null) {
                    nodeQueue.add(n.getLeft());
                    pathQueue.add(path + n.getLeft().getVal().toString());
                }
                if (n.getRight() != null) {
                    nodeQueue.add(n.getRight());
                    pathQueue.add(path + n.getRight().getVal().toString());
                }
            }
        }
        return paths;
    }
}
